package com.zofer.study.linkedlist;

import java.util.Stack;

/**
 * 题目：给定一个链表，请判断该链表是否为回文结构。然后再逐一出栈与链表元素对比。
 *
 */
public class IsPail {

    /**
     * 思路：我们可以利用栈来做辅助，把链表的节点全部入栈，在一个一个出栈与链表进行对比
     * 这种解法比较简单，时间复杂度为 O(n), 空间复杂度为 O(n)。
     */
    public boolean isPail (ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }

        ListNode temp = head;
        Stack<ListNode> stack = new Stack<>();

        while (temp != null) {
            stack.push(temp);
            temp = temp.next;
        }

        while (!stack.isEmpty()) {
            ListNode t = stack.pop();
            if (t.val != head.val) {
                return false;
            }
            head = head.next;
        }
        return true;
    }


    /**
     * 解法2：
     * 真的需要全部入栈吗？其实我们也可以让链表的后半部分入栈就可以了，然后把栈中的元素与链表的前半部分对比
     * 然后逐个出栈，与链表的前半部分(1->2)对比。这样做的话空间复杂度会减少一半。
     * https://blog.51cto.com/15015171/2555345
     */


    /**
     * 解法3：
     * 上道题我们有作过链表的反转的，没看过的可以看一下勒：【链表问题】如何优雅着反转单链表]，
     * 我们可以把链表的后半部分进行反转，然后再用后半部分与前半部分进行比较就可以了。
     * 这种做法额外空间复杂度只需要 O(1), 时间复杂度为 O(n)。
     * https://blog.51cto.com/15015171/2555345
     */
}
